package lc;
import java.util.*;
import org.junit.*;
public class Ex1552 {
    class Solution {
        public int maxDistance(int[] position, int m) {
            int min = Integer.MAX_VALUE, max = 0;
            for (int i = 0; i < position.length; i++) {
                max = Math.max(max, position[i]);
                min = Math.min(min, position[i]);
            }
            Arrays.sort(position); //便于计算count
            int lo = 1, hi = max - min; //position各不相同，因此最小差值为1，最大差值就是绝对值相差最大的
    
            //f(x)表示，当允许的最小磁力最大为x时，所能存放的球的数量
            //当x越大，存放起来越困难，能够存放的数量越少，为单调递减函数
            while (lo < hi) {
                int mid = (hi - lo + 1) / 2 + lo;
                int cnt = count(position, mid);
                System.out.println(lo + "\t" + mid + "\t" + hi + "\t" + cnt);
                if (cnt < m) {
                    //此差距下，无法满足m个球，缩小范围
                    hi = mid - 1;
                } else {
                    lo = mid; //找最优
                }
            }
            return lo;
        }
    
        private int count(int[] nums, int m) {
            int cnt = 1; //至少可以放一个
            //第一个放在最左边
            int last = nums[0];
            for (int i = 1; i < nums.length; i++) {
                if (nums[i] - last >= m) {
                    //这里放一个
                    cnt++;
                    last = nums[i];
                }
            }
            return cnt;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        int[] nums = new int[]{1,2,3,5,7};
        StringBuilder sb = new StringBuilder();
        // sb.setLength(newLength);
        System.out.println(s.count(nums, 3));
    }
    /**
        
    1	3	6	3
    3	2	6	3
    2	3	6	3
    3	2	6	3
    2	3	6	3


     */
}
